package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;
import org.omg.CORBA.INTERNAL;

import java.util.*;

/*
用栈(迭代法)深度优先遍历二叉树
 */
public class Of20210116QueryTreeByStack {
    public static void main(String[] args) {
        System.out.println(inorderTraversal(new TreeNode(1, new TreeNode(2, new TreeNode(4)
                , new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)))));
    }

    /*
    前序遍历
     */
    private static List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> result = new ArrayList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop != null)
                result.add(pop.val);
            else continue;
            stack.push(pop.right);
            stack.push(pop.left);
        }
        return result;
    }

    /*
    中序遍历
     */
    private static List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) { // 指针来访问节点，访问到最底层
                stack.push(cur); // 讲访问的节点放进栈
                cur = cur.left;                // 左
            } else {
                cur = stack.pop(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                result.add(cur.val);     // 中
                cur = cur.right;               // 右
            }
        }
        return result;
    }

    /*
    后序遍历
     */
    private static List<Integer> postorderTraversal(TreeNode root){
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            if (pop!=null)
                result.add(pop.val);
            else continue;
            stack.push(pop.left);
            stack.push(pop.right);
        }
        Collections.reverse(result);
        return result;

    }
}
